{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Rank Transform of a Matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #union-find #graph #topological-sort #array #matrix #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #并查集 #图 #拓扑排序 #数组 #矩阵 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: matrixRankTransform"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #矩阵转换后的秩"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <code>m x n</code> 的矩阵 <code>matrix</code> ，请你返回一个新的矩阵<em> </em><code>answer</code> ，其中<em> </em><code>answer[row][col]</code> 是 <code>matrix[row][col]</code> 的秩。</p>\n",
    "\n",
    "<p>每个元素的 <b>秩</b> 是一个整数，表示这个元素相对于其他元素的大小关系，它按照如下规则计算：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>秩是从 1 开始的一个整数。</li>\n",
    "\t<li>如果两个元素 <code>p</code> 和 <code>q</code> 在 <strong>同一行</strong> 或者 <strong>同一列</strong> ，那么：\n",
    "\t<ul>\n",
    "\t\t<li>如果 <code>p < q</code> ，那么 <code>rank(p) < rank(q)</code></li>\n",
    "\t\t<li>如果 <code>p == q</code> ，那么 <code>rank(p) == rank(q)</code></li>\n",
    "\t\t<li>如果 <code>p > q</code> ，那么 <code>rank(p) > rank(q)</code></li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "\t<li><b>秩</b> 需要越 <strong>小</strong> 越好。</li>\n",
    "</ul>\n",
    "\n",
    "<p>题目保证按照上面规则 <code>answer</code> 数组是唯一的。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/10/25/rank1.jpg\" style=\"width: 442px; height: 162px;\" />\n",
    "<pre>\n",
    "<b>输入：</b>matrix = [[1,2],[3,4]]\n",
    "<b>输出：</b>[[1,2],[2,3]]\n",
    "<strong>解释：</strong>\n",
    "matrix[0][0] 的秩为 1 ，因为它是所在行和列的最小整数。\n",
    "matrix[0][1] 的秩为 2 ，因为 matrix[0][1] > matrix[0][0] 且 matrix[0][0] 的秩为 1 。\n",
    "matrix[1][0] 的秩为 2 ，因为 matrix[1][0] > matrix[0][0] 且 matrix[0][0] 的秩为 1 。\n",
    "matrix[1][1] 的秩为 3 ，因为 matrix[1][1] > matrix[0][1]， matrix[1][1] > matrix[1][0] 且 matrix[0][1] 和 matrix[1][0] 的秩都为 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/10/25/rank2.jpg\" style=\"width: 442px; height: 162px;\" />\n",
    "<pre>\n",
    "<b>输入：</b>matrix = [[7,7],[7,7]]\n",
    "<b>输出：</b>[[1,1],[1,1]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/10/25/rank3.jpg\" style=\"width: 601px; height: 322px;\" />\n",
    "<pre>\n",
    "<b>输入：</b>matrix = [[20,-21,14],[-19,4,19],[22,-47,24],[-19,4,19]]\n",
    "<b>输出：</b>[[4,2,3],[1,3,4],[5,1,6],[1,3,4]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/10/25/rank4.jpg\" style=\"width: 601px; height: 242px;\" />\n",
    "<pre>\n",
    "<b>输入：</b>matrix = [[7,3,6],[1,4,5],[9,8,2]]\n",
    "<b>输出：</b>[[5,1,4],[1,2,3],[6,3,1]]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == matrix.length</code></li>\n",
    "\t<li><code>n == matrix[i].length</code></li>\n",
    "\t<li><code>1 <= m, n <= 500</code></li>\n",
    "\t<li><code>-10<sup>9</sup> <= matrix[row][col] <= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [rank-transform-of-a-matrix](https://leetcode.cn/problems/rank-transform-of-a-matrix/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [rank-transform-of-a-matrix](https://leetcode.cn/problems/rank-transform-of-a-matrix/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2],[3,4]]', '[[7,7],[7,7]]', '[[20,-21,14],[-19,4,19],[22,-47,24],[-19,4,19]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixRankTransform(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "\n",
    "        rows = []\n",
    "        cols = []\n",
    "\n",
    "        fa = [i for i in range(m * n)]\n",
    "\n",
    "        def find(i):\n",
    "            if i == fa[i]:\n",
    "                return i\n",
    "            else:\n",
    "                fa[i] = find(fa[i])\n",
    "\n",
    "                return fa[i]\n",
    "\n",
    "        def merge(i, j):\n",
    "            fa[find(i)] = find(j)\n",
    "\n",
    "        for i in range(m):\n",
    "            s = defaultdict(list)\n",
    "            for j in range(n):\n",
    "                s[matrix[i][j]].append(i * n + j)\n",
    "\n",
    "            for sames in s.values():\n",
    "                x = sames[0]\n",
    "                for y in sames[1:]:\n",
    "                    merge(x, y)\n",
    "\n",
    "        for j in range(n):\n",
    "            s = defaultdict(list)\n",
    "            for i in range(m):\n",
    "                s[matrix[i][j]].append(i * n + j)\n",
    "\n",
    "            for sames in s.values():\n",
    "                x = sames[0]\n",
    "                for y in sames[1:]:\n",
    "                    merge(x, y)\n",
    "\n",
    "        g = defaultdict(list)\n",
    "        ind = defaultdict(int)\n",
    "\n",
    "        for i in range(m):\n",
    "            s = {}\n",
    "\n",
    "            for j in range(n):\n",
    "                s[matrix[i][j]] = j\n",
    "\n",
    "            keys = sorted(s.keys())\n",
    "            for k in range(len(keys) - 1):\n",
    "                j = s[keys[k]]\n",
    "                j1 = s[keys[k + 1]]\n",
    "\n",
    "                g[find(i * n + j)].append(find(i * n + j1))\n",
    "                ind[find(i * n + j1)] += 1\n",
    "\n",
    "        for j in range(n):\n",
    "            s = {}\n",
    "\n",
    "            for i in range(m):\n",
    "                s[matrix[i][j]] = i\n",
    "\n",
    "            keys = sorted(s.keys())\n",
    "            for k in range(len(keys) - 1):\n",
    "                i = s[keys[k]]\n",
    "                i1 = s[keys[k + 1]]\n",
    "\n",
    "                g[find(i * n + j)].append(find(i1 * n + j))\n",
    "                ind[find(i1 * n + j)] += 1\n",
    "\n",
    "        ret = [[1] * n for _ in range(m)]\n",
    "        \n",
    "        roots = set()\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if ind[find(i * n + j)] == 0:\n",
    "                    roots.add(find(i * n + j))\n",
    "\n",
    "        q = deque([(x, 1) for x in roots])\n",
    "\n",
    "        rank = {}\n",
    "        while q:\n",
    "            x, r = q.popleft()\n",
    "\n",
    "            rank[x] = r\n",
    "\n",
    "            for y in g[x]:\n",
    "                ind[y] -= 1\n",
    "\n",
    "                if ind[y] == 0:\n",
    "                    q.append((y, r + 1))\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ret[i][j] = rank[find(i * n + j)]\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixRankTransform(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        rank = [0] * (m + n)\n",
    "        \n",
    "        # 对相同的数值进行联接\n",
    "        def find(i, parent):\n",
    "            if i != parent[i]:\n",
    "                parent[i] = find(parent[i], parent)\n",
    "            return parent[i]\n",
    "        \n",
    "        d = collections.defaultdict(list)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                d[matrix[i][j]].append((i, j))\n",
    "        \n",
    "        for val in sorted(d):\n",
    "            parent = list(range(m + n))  \n",
    "            rank2 = rank[:]  \n",
    "            for i, j in d[val]:\n",
    "                i, j = find(i, parent), find(j + m, parent)  \n",
    "                parent[i] = j  \n",
    "                rank2[j] = max(rank2[i], rank2[j])\n",
    "            for i, j in d[val]:\n",
    "                rank[i] = rank[j + m] = matrix[i][j] = rank2[find(i, parent)] + 1\n",
    "                \n",
    "        return matrix\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    class UF:\n",
    "        def __init__(o,n):\n",
    "            o.f=list(range(n))\n",
    "            o.sz=[1]*n\n",
    "        def find(o,x):\n",
    "            if x!=o.f[x]:\n",
    "                o.f[x]=o.find(o.f[x])\n",
    "            return o.f[x]\n",
    "        def union(o,x,y):\n",
    "            fx=o.find(x);fy=o.find(y)\n",
    "            if o.sz[fx]>=o.sz[fy]:\n",
    "                o.f[fy]=fx\n",
    "                o.sz[fx]+=o.sz[fy]\n",
    "            else:\n",
    "                o.f[fx]=fy\n",
    "                o.sz[fy]+=o.sz[fx]\n",
    "        def reset(o,x,y):\n",
    "            o.f[x]=x;o.f[y]=y\n",
    "            o.sz[x]=o.sz[y]=1\n",
    "\n",
    "    def matrixRankTransform(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        d=defaultdict(list)\n",
    "        for i,r in enumerate(matrix):\n",
    "            for j,v in enumerate(r):\n",
    "                d[v].append((i,j))\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        u = Solution.UF(m + n)\n",
    "        rx,cx,rk,ans=[0]*m,[0]*n,[0]*(m+n),[[0]*n for _ in range(m)]\n",
    "        for v in sorted(d):\n",
    "            a=d[v]\n",
    "            for x,y in a:u.union(x,y+m)\n",
    "            for x,y in a:rk[u.find(x)]=max(rk[u.find(x)],max(rx[x],cx[y]))\n",
    "            for x,y in a:ans[x][y]=rx[x]=cx[y]=1+rk[u.find(x)]\n",
    "            for x,y in a:u.reset(x,y+m)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    class UF:\n",
    "        def __init__(o,n):\n",
    "            o.f=list(range(n))\n",
    "            o.sz=[1]*n\n",
    "        def find(o,x):\n",
    "            if x!=o.f[x]:\n",
    "                o.f[x]=o.find(o.f[x])\n",
    "            return o.f[x]\n",
    "        def union(o,x,y):\n",
    "            fx=o.find(x);fy=o.find(y)\n",
    "            if o.sz[fx]>=o.sz[fy]:\n",
    "                o.f[fy]=fx\n",
    "                o.sz[fx]+=o.sz[fy]\n",
    "            else:\n",
    "                o.f[fx]=fy\n",
    "                o.sz[fy]+=o.sz[fx]\n",
    "        def reset(o,x,y):\n",
    "            o.f[x]=x;o.f[y]=y\n",
    "            o.sz[x]=o.sz[y]=1\n",
    "\n",
    "    def matrixRankTransform(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        d=defaultdict(list)\n",
    "        for i,r in enumerate(matrix):\n",
    "            for j,v in enumerate(r):\n",
    "                #if v not in d:d[v]=[]\n",
    "                d[v].append((i,j))\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        u = Solution.UF(m + n)\n",
    "        rx,cx,rk,ans=[0]*m,[0]*n,[0]*(m+n),[[0]*n for _ in range(m)]\n",
    "        for v in sorted(d):\n",
    "            a=d[v]\n",
    "            for x,y in a:u.union(x,y+m)\n",
    "            for x,y in a:rk[u.find(x)]=max(rk[u.find(x)],max(rx[x],cx[y]))\n",
    "            for x,y in a:ans[x][y]=rx[x]=cx[y]=1+rk[u.find(x)]\n",
    "            for x,y in a:u.reset(x,y+m)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedDict\n",
    "class Solution:\n",
    "    class UF:\n",
    "        def __init__(o,n):o.f=list(range(n));o.sz=[1]*n\n",
    "        def find(o,x):\n",
    "            if x!=o.f[x]:o.f[x]=o.find(o.f[x])\n",
    "            return o.f[x]\n",
    "        def union(o,x,y):\n",
    "            fx=o.find(x);fy=o.find(y)\n",
    "            if o.sz[fx]>=o.sz[fy]:o.f[fy]=fx;o.sz[fx]+=o.sz[fy]\n",
    "            else:o.f[fx]=fy;o.sz[fy]+=o.sz[fx]\n",
    "        def reset(o,x,y):o.f[x]=x;o.f[y]=y;o.sz[x]=o.sz[y]=1\n",
    "\n",
    "    def matrixRankTransform(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        d = SortedDict()\n",
    "        for i, r in enumerate(matrix):\n",
    "            for j, v in enumerate(r):\n",
    "                if v not in d: d[v] = []\n",
    "                d[v].append((i, j))\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        u, rx, cx, rk, ans = Solution.UF(m + n), [0] * m, [0] * n, [0] * (m + n), [[0] * n for _ in range(m)]\n",
    "        for a in d.values():\n",
    "            for x, y in a: u.union(x, y + m)\n",
    "            for x, y in a: rk[u.find(x)] = max(rk[u.find(x)], max(rx[x], cx[y]))\n",
    "            for x, y in a: ans[x][y] = rx[x] = cx[y] = 1 + rk[u.find(x)]\n",
    "            for x, y in a: u.reset(x, y + m)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedDict\n",
    "class Solution:\n",
    "    class UF:\n",
    "        def __init__(o,n):\n",
    "            o.f=list(range(n))\n",
    "            o.sz=[1]*n\n",
    "        def find(o,x):\n",
    "            if x!=o.f[x]:\n",
    "                o.f[x]=o.find(o.f[x])\n",
    "            return o.f[x]\n",
    "        def union(o,x,y):\n",
    "            fx=o.find(x);fy=o.find(y)\n",
    "            if o.sz[fx]>=o.sz[fy]:\n",
    "                o.f[fy]=fx\n",
    "                o.sz[fx]+=o.sz[fy]\n",
    "            else:\n",
    "                o.f[fx]=fy\n",
    "                o.sz[fy]+=o.sz[fx]\n",
    "        def reset(o,x,y):\n",
    "            o.f[x]=x;o.f[y]=y\n",
    "            o.sz[x]=o.sz[y]=1\n",
    "\n",
    "    def matrixRankTransform(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        d=SortedDict()\n",
    "        for i,r in enumerate(matrix):\n",
    "            for j,v in enumerate(r):\n",
    "                if v not in d:d[v]=[]\n",
    "                d[v].append((i,j))\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        u = Solution.UF(m + n)\n",
    "        rx,cx,rk,ans=[0]*m,[0]*n,[0]*(m+n),[[0]*n for _ in range(m)]\n",
    "        for a in d.values():\n",
    "            for x,y in a:u.union(x,y+m)\n",
    "            for x,y in a:rk[u.find(x)]=max(rk[u.find(x)],max(rx[x],cx[y]))\n",
    "            for x,y in a:ans[x][y]=rx[x]=cx[y]=1+rk[u.find(x)]\n",
    "            for x,y in a:u.reset(x,y+m)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList, SortedDict\n",
    "\n",
    "class Solution:\n",
    "    class UF:\n",
    "        def __init__(o,n):\n",
    "            o.f=list(range(n))\n",
    "            o.sz=[1]*n\n",
    "        def find(o,x):\n",
    "            if x!=o.f[x]:\n",
    "                o.f[x]=o.find(o.f[x])\n",
    "            return o.f[x]\n",
    "        def union(o,x,y):\n",
    "            fx=o.find(x);fy=o.find(y)\n",
    "            if o.sz[fx]>=o.sz[fy]:\n",
    "                o.f[fy]=fx\n",
    "                o.sz[fx]+=o.sz[fy]\n",
    "            else:\n",
    "                o.f[fx]=fy\n",
    "                o.sz[fy]+=o.sz[fx]\n",
    "        def reset(o,x,y):\n",
    "            o.f[x]=x;o.f[y]=y\n",
    "            o.sz[x]=o.sz[y]=1\n",
    "\n",
    "    def matrixRankTransform(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        d=SortedDict()\n",
    "        for i,r in enumerate(matrix):\n",
    "            for j,v in enumerate(r):\n",
    "                if v not in d:d[v]=[]\n",
    "                d[v].append((i,j))\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        u = Solution.UF(m + n)\n",
    "        rx,cx,rk,ans=[0]*m,[0]*n,[0]*(m+n),[[0]*n for _ in range(m)]\n",
    "        for a in d.values():\n",
    "            for x,y in a:u.union(x,y+m)\n",
    "            for x,y in a:rk[u.find(x)]=max(rk[u.find(x)],max(rx[x],cx[y]))\n",
    "            for x,y in a:ans[x][y]=rx[x]=cx[y]=1+rk[u.find(x)]\n",
    "            for x,y in a:u.reset(x,y+m)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList, SortedDict\n",
    "class Solution:\n",
    "    class UF:\n",
    "        def __init__(o,n):o.f=list(range(n));o.sz=[1]*n\n",
    "        def find(o,x):\n",
    "            if x!=o.f[x]:o.f[x]=o.find(o.f[x])\n",
    "            return o.f[x]\n",
    "        def union(o,x,y):\n",
    "            fx=o.find(x);fy=o.find(y)\n",
    "            if o.sz[fx]>=o.sz[fy]:o.f[fy]=fx;o.sz[fx]+=o.sz[fy]\n",
    "            else:o.f[fx]=fy;o.sz[fy]+=o.sz[fx]\n",
    "        def reset(o,x,y):o.f[x]=x;o.f[y]=y;o.sz[x]=o.sz[y]=1\n",
    "\n",
    "    def matrixRankTransform(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        d = SortedDict()\n",
    "        for i, r in enumerate(matrix):\n",
    "            for j, v in enumerate(r):\n",
    "                if v not in d: d[v] = []\n",
    "                d[v].append((i, j))\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        u, rx, cx, rk, ans = Solution.UF(m + n), [0] * m, [0] * n, [0] * (m + n), [[0] * n for _ in range(m)]\n",
    "        for a in d.values():\n",
    "            for x, y in a: u.union(x, y + m)\n",
    "            for x, y in a: rk[u.find(x)] = max(rk[u.find(x)], max(rx[x], cx[y]))\n",
    "            for x, y in a: ans[x][y] = rx[x] = cx[y] = 1 + rk[u.find(x)]\n",
    "            for x, y in a: u.reset(x, y + m)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixRankTransform(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        ref = defaultdict(list)\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ref[matrix[i][j]].append((i, j))\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        row = [0] * m\n",
    "        col = [0] * n\n",
    "        for i in sorted(ref.keys()):\n",
    "            x_y = defaultdict(list)\n",
    "            y_x = defaultdict(list)\n",
    "            for x, y in ref[i]:\n",
    "                x_y[x].append(y)\n",
    "                y_x[y].append(x)\n",
    "            ref_x = {}\n",
    "            for x, y in ref[i]:\n",
    "                target = -inf\n",
    "                if x not in ref_x:\n",
    "                    que = deque()\n",
    "                    que.append(x)\n",
    "                    visited = set()\n",
    "                    visitedy = set()\n",
    "                    visited.add(x)\n",
    "                    target = max(target, col[y])\n",
    "                    target = max(target, row[x])\n",
    "                    while que:\n",
    "                        p = que.popleft()\n",
    "                        for q in x_y[p]:\n",
    "                            target = max(target, col[q])\n",
    "                            if q not in visitedy:\n",
    "                                visitedy.add(q)\n",
    "                            else:\n",
    "                                continue\n",
    "                            for r in y_x[q]:\n",
    "                                if r not in visited:\n",
    "                                    que.append(r)\n",
    "                                    visited.add(r)\n",
    "                                    target = max(target, row[r])\n",
    "                    for p in visited:\n",
    "                        ref_x[p] = target + 1\n",
    "                    ans[x][y] = target + 1\n",
    "                    row[x] = target + 1\n",
    "                    col[y] = target + 1\n",
    "                else:\n",
    "                    ans[x][y] = ref_x[x]\n",
    "                    row[x] = ref_x[x]\n",
    "                    col[y] = ref_x[x]\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixRankTransform(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        uf = UnionFind(m, n)\n",
    "        for i, row in enumerate(matrix):\n",
    "            num2indexList = defaultdict(list)\n",
    "            for j, num in enumerate(row):\n",
    "                num2indexList[num].append([i, j])\n",
    "            for indexList in num2indexList.values():\n",
    "                i1, j1 = indexList[0]\n",
    "                for k in range(1, len(indexList)):\n",
    "                    i2, j2 = indexList[k]\n",
    "                    uf.union(i1, j1, i2, j2)\n",
    "        for j in range(n):\n",
    "            num2indexList = defaultdict(list)\n",
    "            for i in range(m):\n",
    "                num2indexList[matrix[i][j]].append([i, j])\n",
    "            for indexList in num2indexList.values():\n",
    "                i1, j1 = indexList[0]\n",
    "                for k in range(1, len(indexList)):\n",
    "                    i2, j2 = indexList[k]\n",
    "                    uf.union(i1, j1, i2, j2)\n",
    "\n",
    "        degree = Counter()\n",
    "        adj = defaultdict(list)\n",
    "        for i, row in enumerate(matrix):\n",
    "            num2index = {}\n",
    "            for j, num in enumerate(row):\n",
    "                num2index[num] = (i, j)\n",
    "            sortedArray = sorted(num2index.keys())\n",
    "            for k in range(1, len(sortedArray)):\n",
    "                i1, j1 = num2index[sortedArray[k - 1]]\n",
    "                i2, j2 = num2index[sortedArray[k]]\n",
    "                ri1, rj1 = uf.find(i1, j1)\n",
    "                ri2, rj2 = uf.find(i2, j2)\n",
    "                degree[(ri2, rj2)] += 1\n",
    "                adj[(ri1, rj1)].append([ri2, rj2])\n",
    "        for j in range(n):\n",
    "            num2index = {}\n",
    "            for i in range(m):\n",
    "                num = matrix[i][j]\n",
    "                num2index[num] = (i, j)\n",
    "            sortedArray = sorted(num2index.keys())\n",
    "            for k in range(1, len(sortedArray)):\n",
    "                i1, j1 = num2index[sortedArray[k - 1]]\n",
    "                i2, j2 = num2index[sortedArray[k]]\n",
    "                ri1, rj1 = uf.find(i1, j1)\n",
    "                ri2, rj2 = uf.find(i2, j2)\n",
    "                degree[(ri2, rj2)] += 1\n",
    "                adj[(ri1, rj1)].append([ri2, rj2])\n",
    "        \n",
    "        rootSet = set()\n",
    "        ranks = {}\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ri, rj = uf.find(i, j)\n",
    "                rootSet.add((ri, rj))\n",
    "                ranks[(ri, rj)] = 1\n",
    "        q = deque([[i, j] for i, j in rootSet if degree[(i, j)] == 0])\n",
    "        while q:\n",
    "            i, j = q.popleft()\n",
    "            for ui, uj in adj[(i, j)]:\n",
    "                degree[(ui, uj)] -= 1\n",
    "                if degree[(ui, uj)] == 0:\n",
    "                    q.append([ui, uj])\n",
    "                ranks[(ui, uj)] = max(ranks[(ui, uj)], ranks[(i, j)] + 1)\n",
    "        res = [[1] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ri, rj = uf.find(i, j)\n",
    "                res[i][j] = ranks[(ri, rj)]\n",
    "        return res\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, m, n):\n",
    "        self.m = m\n",
    "        self.n = n\n",
    "        self.root = [[[i, j] for j in range(n)] for i in range(m)]\n",
    "        self.size = [[1] * n for _ in range(m)]\n",
    "\n",
    "    def find(self, i, j):\n",
    "        ri, rj = self.root[i][j]\n",
    "        if [ri, rj] == [i, j]:\n",
    "            return [i, j]\n",
    "        self.root[i][j] = self.find(ri, rj)\n",
    "        return self.root[i][j]\n",
    "\n",
    "    def union(self, i1, j1, i2, j2):\n",
    "        ri1, rj1 = self.find(i1, j1)\n",
    "        ri2, rj2 = self.find(i2, j2)\n",
    "        if [ri1, rj1] != [ri2, rj2]:\n",
    "            if self.size[ri1][rj1] >= self.size[ri2][rj2]:\n",
    "                self.root[ri2][rj2] = [ri1, rj1]\n",
    "                self.size[ri1][rj1] += self.size[ri2][rj2]\n",
    "            else:\n",
    "                self.root[ri1][rj1] = [ri2, rj2]\n",
    "                self.size[ri2][rj2] += self.size[ri1][rj1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixRankTransform(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        uf = UnionFind(m, n)\n",
    "        for i, row in enumerate(matrix):\n",
    "            num2indexList = defaultdict(list)\n",
    "            for j, num in enumerate(row):\n",
    "                num2indexList[num].append([i, j])\n",
    "            for indexList in num2indexList.values():\n",
    "                i1, j1 = indexList[0]\n",
    "                for k in range(1, len(indexList)):\n",
    "                    i2, j2 = indexList[k]\n",
    "                    uf.union(i1, j1, i2, j2)\n",
    "        for j in range(n):\n",
    "            num2indexList = defaultdict(list)\n",
    "            for i in range(m):\n",
    "                num2indexList[matrix[i][j]].append([i, j])\n",
    "            for indexList in num2indexList.values():\n",
    "                i1, j1 = indexList[0]\n",
    "                for k in range(1, len(indexList)):\n",
    "                    i2, j2 = indexList[k]\n",
    "                    uf.union(i1, j1, i2, j2)\n",
    "\n",
    "        degree = Counter()\n",
    "        adj = defaultdict(list)\n",
    "        for i, row in enumerate(matrix):\n",
    "            num2index = {}\n",
    "            for j, num in enumerate(row):\n",
    "                num2index[num] = (i, j)\n",
    "            sortedArray = sorted(num2index.keys())\n",
    "            for k in range(1, len(sortedArray)):\n",
    "                i1, j1 = num2index[sortedArray[k - 1]]\n",
    "                i2, j2 = num2index[sortedArray[k]]\n",
    "                ri1, rj1 = uf.find(i1, j1)\n",
    "                ri2, rj2 = uf.find(i2, j2)\n",
    "                degree[(ri2, rj2)] += 1\n",
    "                adj[(ri1, rj1)].append([ri2, rj2])\n",
    "        for j in range(n):\n",
    "            num2index = {}\n",
    "            for i in range(m):\n",
    "                num = matrix[i][j]\n",
    "                num2index[num] = (i, j)\n",
    "            sortedArray = sorted(num2index.keys())\n",
    "            for k in range(1, len(sortedArray)):\n",
    "                i1, j1 = num2index[sortedArray[k - 1]]\n",
    "                i2, j2 = num2index[sortedArray[k]]\n",
    "                ri1, rj1 = uf.find(i1, j1)\n",
    "                ri2, rj2 = uf.find(i2, j2)\n",
    "                degree[(ri2, rj2)] += 1\n",
    "                adj[(ri1, rj1)].append([ri2, rj2])\n",
    "        \n",
    "        rootSet = set()\n",
    "        ranks = {}\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ri, rj = uf.find(i, j)\n",
    "                rootSet.add((ri, rj))\n",
    "                ranks[(ri, rj)] = 1\n",
    "        q = deque([[i, j] for i, j in rootSet if degree[(i, j)] == 0])\n",
    "        while q:\n",
    "            i, j = q.popleft()\n",
    "            for ui, uj in adj[(i, j)]:\n",
    "                degree[(ui, uj)] -= 1\n",
    "                if degree[(ui, uj)] == 0:\n",
    "                    q.append([ui, uj])\n",
    "                ranks[(ui, uj)] = max(ranks[(ui, uj)], ranks[(i, j)] + 1)\n",
    "        res = [[1] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ri, rj = uf.find(i, j)\n",
    "                res[i][j] = ranks[(ri, rj)]\n",
    "        return res\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, m, n):\n",
    "        self.m = m\n",
    "        self.n = n\n",
    "        self.root = [[[i, j] for j in range(n)] for i in range(m)]\n",
    "        self.size = [[1] * n for _ in range(m)]\n",
    "\n",
    "    def find(self, i, j):\n",
    "        ri, rj = self.root[i][j]\n",
    "        if [ri, rj] == [i, j]:\n",
    "            return [i, j]\n",
    "        self.root[i][j] = self.find(ri, rj)\n",
    "        return self.root[i][j]\n",
    "\n",
    "    def union(self, i1, j1, i2, j2):\n",
    "        ri1, rj1 = self.find(i1, j1)\n",
    "        ri2, rj2 = self.find(i2, j2)\n",
    "        if [ri1, rj1] != [ri2, rj2]:\n",
    "            if self.size[ri1][rj1] >= self.size[ri2][rj2]:\n",
    "                self.root[ri2][rj2] = [ri1, rj1]\n",
    "                self.size[ri1][rj1] += self.size[ri2][rj2]\n",
    "            else:\n",
    "                self.root[ri1][rj1] = [ri2, rj2]\n",
    "                self.size[ri2][rj2] += self.size[ri1][rj1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixRankTransform(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        uf = UnionFind(m, n)\n",
    "        for i, row in enumerate(matrix):\n",
    "            num2indexList = defaultdict(list)\n",
    "            for j, num in enumerate(row):\n",
    "                num2indexList[num].append([i, j])\n",
    "            for indexList in num2indexList.values():\n",
    "                i1, j1 = indexList[0]\n",
    "                for k in range(1, len(indexList)):\n",
    "                    i2, j2 = indexList[k]\n",
    "                    uf.union(i1, j1, i2, j2)\n",
    "        for j in range(n):\n",
    "            num2indexList = defaultdict(list)\n",
    "            for i in range(m):\n",
    "                num2indexList[matrix[i][j]].append([i, j])\n",
    "            for indexList in num2indexList.values():\n",
    "                i1, j1 = indexList[0]\n",
    "                for k in range(1, len(indexList)):\n",
    "                    i2, j2 = indexList[k]\n",
    "                    uf.union(i1, j1, i2, j2)\n",
    "\n",
    "        degree = Counter()\n",
    "        adj = defaultdict(list)\n",
    "        for i, row in enumerate(matrix):\n",
    "            num2index = {}\n",
    "            for j, num in enumerate(row):\n",
    "                num2index[num] = (i, j)\n",
    "            sortedArray = sorted(num2index.keys())\n",
    "            for k in range(1, len(sortedArray)):\n",
    "                i1, j1 = num2index[sortedArray[k - 1]]\n",
    "                i2, j2 = num2index[sortedArray[k]]\n",
    "                ri1, rj1 = uf.find(i1, j1)\n",
    "                ri2, rj2 = uf.find(i2, j2)\n",
    "                degree[(ri2, rj2)] += 1\n",
    "                adj[(ri1, rj1)].append([ri2, rj2])\n",
    "        for j in range(n):\n",
    "            num2index = {}\n",
    "            for i in range(m):\n",
    "                num = matrix[i][j]\n",
    "                num2index[num] = (i, j)\n",
    "            sortedArray = sorted(num2index.keys())\n",
    "            for k in range(1, len(sortedArray)):\n",
    "                i1, j1 = num2index[sortedArray[k - 1]]\n",
    "                i2, j2 = num2index[sortedArray[k]]\n",
    "                ri1, rj1 = uf.find(i1, j1)\n",
    "                ri2, rj2 = uf.find(i2, j2)\n",
    "                degree[(ri2, rj2)] += 1\n",
    "                adj[(ri1, rj1)].append([ri2, rj2])\n",
    "        \n",
    "        rootSet = set()\n",
    "        ranks = {}\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ri, rj = uf.find(i, j)\n",
    "                rootSet.add((ri, rj))\n",
    "                ranks[(ri, rj)] = 1\n",
    "        q = deque([[i, j] for i, j in rootSet if degree[(i, j)] == 0])\n",
    "        while q:\n",
    "            i, j = q.popleft()\n",
    "            for ui, uj in adj[(i, j)]:\n",
    "                degree[(ui, uj)] -= 1\n",
    "                if degree[(ui, uj)] == 0:\n",
    "                    q.append([ui, uj])\n",
    "                ranks[(ui, uj)] = max(ranks[(ui, uj)], ranks[(i, j)] + 1)\n",
    "        res = [[1] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ri, rj = uf.find(i, j)\n",
    "                res[i][j] = ranks[(ri, rj)]\n",
    "        return res\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, m, n):\n",
    "        self.m = m\n",
    "        self.n = n\n",
    "        self.root = [[[i, j] for j in range(n)] for i in range(m)]\n",
    "        self.size = [[1] * n for _ in range(m)]\n",
    "\n",
    "    def find(self, i, j):\n",
    "        ri, rj = self.root[i][j]\n",
    "        if [ri, rj] == [i, j]:\n",
    "            return [i, j]\n",
    "        self.root[i][j] = self.find(ri, rj)\n",
    "        return self.root[i][j]\n",
    "\n",
    "    def union(self, i1, j1, i2, j2):\n",
    "        ri1, rj1 = self.find(i1, j1)\n",
    "        ri2, rj2 = self.find(i2, j2)\n",
    "        if [ri1, rj1] != [ri2, rj2]:\n",
    "            if self.size[ri1][rj1] >= self.size[ri2][rj2]:\n",
    "                self.root[ri2][rj2] = [ri1, rj1]\n",
    "                self.size[ri1][rj1] += self.size[ri2][rj2]\n",
    "            else:\n",
    "                self.root[ri1][rj1] = [ri2, rj2]\n",
    "                self.size[ri2][rj2] += self.size[ri1][rj1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "# 按照各行中相同的元素和各列中相同的元素进行合并后，需要求出各个集合的秩。\n",
    "\n",
    "    def matrixRankTransform(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        uf = UnionFind(m, n)\n",
    "        for i, row in enumerate(matrix):\n",
    "            num2indexList = defaultdict(list)\n",
    "            for j, num in enumerate(row):\n",
    "                num2indexList[num].append([i, j])\n",
    "            for indexList in num2indexList.values():\n",
    "                i1, j1 = indexList[0]\n",
    "                for k in range(1, len(indexList)):\n",
    "                    i2, j2 = indexList[k]\n",
    "                    uf.union(i1, j1, i2, j2)\n",
    "        for j in range(n):\n",
    "            num2indexList = defaultdict(list)\n",
    "            for i in range(m):\n",
    "                num2indexList[matrix[i][j]].append([i, j])\n",
    "            for indexList in num2indexList.values():\n",
    "                i1, j1 = indexList[0]\n",
    "                for k in range(1, len(indexList)):\n",
    "                    i2, j2 = indexList[k]\n",
    "                    uf.union(i1, j1, i2, j2)\n",
    "\n",
    "# 将每行每列的元素进行去重排序，如果有 kkk 个不重复元素，只需建立 (k−1)(k-1)(k−1) 条单向边，即可表示出大小关系。\n",
    "        degree = Counter()\n",
    "        adj = defaultdict(list)\n",
    "        for i, row in enumerate(matrix):\n",
    "            num2index = {}\n",
    "            for j, num in enumerate(row):\n",
    "                num2index[num] = (i, j)\n",
    "            sortedArray = sorted(num2index.keys())\n",
    "            for k in range(1, len(sortedArray)):\n",
    "                i1, j1 = num2index[sortedArray[k - 1]]\n",
    "                i2, j2 = num2index[sortedArray[k]]\n",
    "                ri1, rj1 = uf.find(i1, j1)\n",
    "                ri2, rj2 = uf.find(i2, j2)\n",
    "                degree[(ri2, rj2)] += 1\n",
    "                adj[(ri1, rj1)].append([ri2, rj2])\n",
    "        for j in range(n):\n",
    "            num2index = {}\n",
    "            for i in range(m):\n",
    "                num = matrix[i][j]\n",
    "                num2index[num] = (i, j)\n",
    "            sortedArray = sorted(num2index.keys())\n",
    "            for k in range(1, len(sortedArray)):\n",
    "                i1, j1 = num2index[sortedArray[k - 1]]\n",
    "                i2, j2 = num2index[sortedArray[k]]\n",
    "                ri1, rj1 = uf.find(i1, j1)\n",
    "                ri2, rj2 = uf.find(i2, j2)\n",
    "                degree[(ri2, rj2)] += 1\n",
    "                adj[(ri1, rj1)].append([ri2, rj2])\n",
    "        \n",
    "        rootSet = set()\n",
    "        ranks = {}\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ri, rj = uf.find(i, j)\n",
    "                rootSet.add((ri, rj))\n",
    "                ranks[(ri, rj)] = 1\n",
    "        q = deque([[i, j] for i, j in rootSet if degree[(i, j)] == 0])\n",
    "        while q:\n",
    "            i, j = q.popleft()\n",
    "            for ui, uj in adj[(i, j)]:\n",
    "                degree[(ui, uj)] -= 1\n",
    "                if degree[(ui, uj)] == 0:\n",
    "                    q.append([ui, uj])\n",
    "                ranks[(ui, uj)] = max(ranks[(ui, uj)], ranks[(i, j)] + 1)\n",
    "        res = [[1] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ri, rj = uf.find(i, j)\n",
    "                res[i][j] = ranks[(ri, rj)]\n",
    "        return res\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, m, n):\n",
    "        self.m = m\n",
    "        self.n = n\n",
    "        self.root = [[[i, j] for j in range(n)] for i in range(m)]\n",
    "        self.size = [[1] * n for _ in range(m)]\n",
    "\n",
    "    def find(self, i, j):\n",
    "        ri, rj = self.root[i][j]\n",
    "        if [ri, rj] == [i, j]:\n",
    "            return [i, j]\n",
    "        self.root[i][j] = self.find(ri, rj)\n",
    "        return self.root[i][j]\n",
    "\n",
    "    def union(self, i1, j1, i2, j2):\n",
    "        ri1, rj1 = self.find(i1, j1)\n",
    "        ri2, rj2 = self.find(i2, j2)\n",
    "        if [ri1, rj1] != [ri2, rj2]:\n",
    "            if self.size[ri1][rj1] >= self.size[ri2][rj2]:\n",
    "                self.root[ri2][rj2] = [ri1, rj1]\n",
    "                self.size[ri1][rj1] += self.size[ri2][rj2]\n",
    "            else:\n",
    "                self.root[ri1][rj1] = [ri2, rj2]\n",
    "                self.size[ri2][rj2] += self.size[ri1][rj1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixRankTransform(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        uf = UnionFind(m, n)\n",
    "        for i, row in enumerate(matrix):\n",
    "            num2indexList = defaultdict(list)\n",
    "            for j, num in enumerate(row):\n",
    "                num2indexList[num].append([i, j])\n",
    "            for indexList in num2indexList.values():\n",
    "                i1, j1 = indexList[0]\n",
    "                for k in range(1, len(indexList)):\n",
    "                    i2, j2 = indexList[k]\n",
    "                    uf.union(i1, j1, i2, j2)\n",
    "        for j in range(n):\n",
    "            num2indexList = defaultdict(list)\n",
    "            for i in range(m):\n",
    "                num2indexList[matrix[i][j]].append([i, j])\n",
    "            for indexList in num2indexList.values():\n",
    "                i1, j1 = indexList[0]\n",
    "                for k in range(1, len(indexList)):\n",
    "                    i2, j2 = indexList[k]\n",
    "                    uf.union(i1, j1, i2, j2)\n",
    "\n",
    "        degree = Counter()\n",
    "        adj = defaultdict(list)\n",
    "        for i, row in enumerate(matrix):\n",
    "            num2index = {}\n",
    "            for j, num in enumerate(row):\n",
    "                num2index[num] = (i, j)\n",
    "            sortedArray = sorted(num2index.keys())\n",
    "            for k in range(1, len(sortedArray)):\n",
    "                i1, j1 = num2index[sortedArray[k - 1]]\n",
    "                i2, j2 = num2index[sortedArray[k]]\n",
    "                ri1, rj1 = uf.find(i1, j1)\n",
    "                ri2, rj2 = uf.find(i2, j2)\n",
    "                degree[(ri2, rj2)] += 1\n",
    "                adj[(ri1, rj1)].append([ri2, rj2])\n",
    "        for j in range(n):\n",
    "            num2index = {}\n",
    "            for i in range(m):\n",
    "                num = matrix[i][j]\n",
    "                num2index[num] = (i, j)\n",
    "            sortedArray = sorted(num2index.keys())\n",
    "            for k in range(1, len(sortedArray)):\n",
    "                i1, j1 = num2index[sortedArray[k - 1]]\n",
    "                i2, j2 = num2index[sortedArray[k]]\n",
    "                ri1, rj1 = uf.find(i1, j1)\n",
    "                ri2, rj2 = uf.find(i2, j2)\n",
    "                degree[(ri2, rj2)] += 1\n",
    "                adj[(ri1, rj1)].append([ri2, rj2])\n",
    "        \n",
    "        rootSet = set()\n",
    "        ranks = {}\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ri, rj = uf.find(i, j)\n",
    "                rootSet.add((ri, rj))\n",
    "                ranks[(ri, rj)] = 1\n",
    "        q = deque([[i, j] for i, j in rootSet if degree[(i, j)] == 0])\n",
    "        while q:\n",
    "            i, j = q.popleft()\n",
    "            for ui, uj in adj[(i, j)]:\n",
    "                degree[(ui, uj)] -= 1\n",
    "                if degree[(ui, uj)] == 0:\n",
    "                    q.append([ui, uj])\n",
    "                ranks[(ui, uj)] = max(ranks[(ui, uj)], ranks[(i, j)] + 1)\n",
    "        res = [[1] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ri, rj = uf.find(i, j)\n",
    "                res[i][j] = ranks[(ri, rj)]\n",
    "        return res\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, m, n):\n",
    "        self.m = m\n",
    "        self.n = n\n",
    "        self.root = [[[i, j] for j in range(n)] for i in range(m)]\n",
    "        self.size = [[1] * n for _ in range(m)]\n",
    "\n",
    "    def find(self, i, j):\n",
    "        ri, rj = self.root[i][j]\n",
    "        if [ri, rj] == [i, j]:\n",
    "            return [i, j]\n",
    "        self.root[i][j] = self.find(ri, rj)\n",
    "        return self.root[i][j]\n",
    "\n",
    "    def union(self, i1, j1, i2, j2):\n",
    "        ri1, rj1 = self.find(i1, j1)\n",
    "        ri2, rj2 = self.find(i2, j2)\n",
    "        if [ri1, rj1] != [ri2, rj2]:\n",
    "            if self.size[ri1][rj1] >= self.size[ri2][rj2]:\n",
    "                self.root[ri2][rj2] = [ri1, rj1]\n",
    "                self.size[ri1][rj1] += self.size[ri2][rj2]\n",
    "            else:\n",
    "                self.root[ri1][rj1] = [ri2, rj2]\n",
    "                self.size[ri2][rj2] += self.size[ri1][rj1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixRankTransform(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        c0 = 600\n",
    "        R, C = len(matrix), len(matrix[0])\n",
    "        dpR, dpC = [0] * R, [0] * C\n",
    "        res = [[0] * C for _ in range(R)]\n",
    "        # 坐标字典\n",
    "        locations = defaultdict(list)\n",
    "        for r, row in enumerate(matrix):\n",
    "            for c, val in enumerate(row):\n",
    "                locations[val].append((r, c))\n",
    "\n",
    "        # 并查集\n",
    "        u = list(range(c0 * 2))\n",
    "        def find(i):\n",
    "            if u[i] == i:\n",
    "                return i\n",
    "            u[i] = find(u[i])\n",
    "            return u[i]\n",
    "        \n",
    "        # 按val从小到大遍历\n",
    "        groups = defaultdict(list)\n",
    "        for val in sorted(locations.keys()):\n",
    "            # 生成并查集，合并行列相同的元素并分组\n",
    "            for r, c in locations[val]:\n",
    "                u[find(r)] = find(c + c0) # 妙啊，因为find的递归生成了一颗树，最终所有行列相同元素的并查集id（find函数返回值）相同\n",
    "            groups.clear()\n",
    "            for r, c in locations[val]:\n",
    "                groups[find(r)].append((r, c)) # 相同并查集id的分成一组\n",
    "\n",
    "            # 同组元素共享相同的rank\n",
    "            for group in groups.values():\n",
    "                rank = max(max(dpR[r], dpC[c]) for r, c in group) + 1\n",
    "                for r, c in group:\n",
    "                    dpR[r] = dpC[c] = res[r][c] = rank\n",
    "                    # 重置并查集\n",
    "                    u[r] = r\n",
    "                    u[c + c0] = c + c0\n",
    "        return res  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixRankTransform(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        # 思路：有行列相同关系的所有相同值共享rank，按照值从小到大生成rank\n",
    "        c0 = 600\n",
    "        R, C = len(matrix), len(matrix[0])\n",
    "        dpR, dpC = [0] * R, [0] * C\n",
    "        res = [[0] * C for _ in range(R)]\n",
    "        # 坐标字典\n",
    "        locations = defaultdict(list)\n",
    "        for r, row in enumerate(matrix):\n",
    "            for c, val in enumerate(row):\n",
    "                locations[val].append((r, c))\n",
    "\n",
    "        # 并查集\n",
    "        u = list(range(c0 * 2))\n",
    "        def find(i):\n",
    "            if u[i] == i:\n",
    "                return i\n",
    "            u[i] = find(u[i])\n",
    "            return u[i]\n",
    "        \n",
    "        # 按val从小到大遍历\n",
    "        groups = defaultdict(list)\n",
    "        for val in sorted(locations.keys()):\n",
    "            # 生成并查集，合并行列相同的元素并分组\n",
    "            for r, c in locations[val]:\n",
    "                u[find(r)] = find(c + c0) # 妙啊，因为find的递归生成了一颗树，最终所有行列相同元素的并查集id（find函数返回值）相同\n",
    "            groups.clear()\n",
    "            for r, c in locations[val]:\n",
    "                groups[find(r)].append((r, c)) # 相同并查集id的分成一组\n",
    "\n",
    "            # 同组元素共享相同的rank\n",
    "            for group in groups.values():\n",
    "                rank = max(max(dpR[r], dpC[c]) for r, c in group) + 1\n",
    "                for r, c in group:\n",
    "                    dpR[r] = dpC[c] = res[r][c] = rank\n",
    "                    # 重置并查集\n",
    "                    u[r] = r\n",
    "                    u[c + c0] = c + c0\n",
    "        return res  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution: \n",
    "    def matrixRankTransform(self, matrix: List[List[int]]) -> List[List[int]]: \n",
    "        print(matrix)\n",
    "        LIM = 512\n",
    "        R, C = len(matrix), len(matrix[0])\n",
    "        res = [[0]*C for _ in range(R)]\n",
    "        countR, countC = [0]*R, [0]*C\n",
    "        \n",
    "        # 按元素大小分别存储元素坐标\n",
    "        ls = collections.defaultdict(list)\n",
    "        for r, row in enumerate(matrix): \n",
    "            for c, val in enumerate(row): \n",
    "                ls[val].append((r, c))\n",
    "                \n",
    "        # 并查集用于合并行或列相同的元素\n",
    "        union = list(range(LIM*2))\n",
    "        def find(i): \n",
    "            if union[i] == i: return i\n",
    "            union[i] = find(union[i])\n",
    "            return union[i]\n",
    "        \n",
    "        # 按val从小到大遍历\n",
    "        pool = collections.defaultdict(list)\n",
    "        for val in sorted(ls.keys()): \n",
    "\n",
    "            # 用并查集合并行和列相同的元素并分组\n",
    "            for r, c in ls[val]: \n",
    "                union[find(r)] = find(c+LIM)\n",
    "            pool.clear()\n",
    "            for r, c in ls[val]: \n",
    "                pool[find(r)].append((r, c))\n",
    "\n",
    "                \n",
    "            # 行和列相同的元素，共享相同的rank\n",
    "            for group in pool.values(): \n",
    "                rank = max(max((countR[r], countC[c])) for r, c in group) + 1\n",
    "                for r, c in group: \n",
    "                    countR[r] = countC[c] = res[r][c] = rank\n",
    "                    # 重置并查集\n",
    "                    union[r] = r\n",
    "                    union[c+LIM] = c+LIM\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution: \n",
    "    def matrixRankTransform(self, matrix: List[List[int]]) -> List[List[int]]: \n",
    "        LIM = 512\n",
    "        R, C = len(matrix), len(matrix[0])\n",
    "        res = [[0]*C for _ in range(R)]\n",
    "        countR, countC = [0]*R, [0]*C\n",
    "        \n",
    "        # 按元素大小分别存储元素坐标\n",
    "        ls = collections.defaultdict(list)\n",
    "        for r, row in enumerate(matrix): \n",
    "            for c, val in enumerate(row): \n",
    "                ls[val].append((r, c))\n",
    "                \n",
    "        # 并查集用于合并行或列相同的元素\n",
    "        union = list(range(LIM*2))\n",
    "        def find(i): \n",
    "            if union[i] == i: return i\n",
    "            union[i] = find(union[i])\n",
    "            return union[i]\n",
    "        \n",
    "        # 按val从小到大遍历\n",
    "        pool = collections.defaultdict(list)\n",
    "        for val in sorted(ls.keys()): \n",
    "\n",
    "            # 用并查集合并行和列相同的元素并分组\n",
    "            for r, c in ls[val]: \n",
    "                union[find(r)] = find(c+LIM)\n",
    "            pool.clear()\n",
    "            for r, c in ls[val]: \n",
    "                pool[find(r)].append((r, c))\n",
    "\n",
    "                \n",
    "            # 行和列相同的元素，共享相同的rank\n",
    "            for group in pool.values(): \n",
    "                rank = max(max((countR[r], countC[c])) for r, c in group) + 1\n",
    "                for r, c in group: \n",
    "                    countR[r] = countC[c] = res[r][c] = rank\n",
    "                    # 重置并查集\n",
    "                    union[r] = r\n",
    "                    union[c+LIM] = c+LIM\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution: \n",
    "    def matrixRankTransform(self, matrix: List[List[int]]) -> List[List[int]]: \n",
    "        LIM = 512\n",
    "        R, C = len(matrix), len(matrix[0])\n",
    "        res = [[0]*C for _ in range(R)]\n",
    "        countR, countC = [0]*R, [0]*C\n",
    "        \n",
    "        # 按元素大小分别存储元素坐标\n",
    "        ls = collections.defaultdict(list)\n",
    "        for r, row in enumerate(matrix): \n",
    "            for c, val in enumerate(row): \n",
    "                ls[val].append((r, c))\n",
    "                \n",
    "        # 并查集用于合并行或列相同的元素\n",
    "        union = list(range(LIM*2))\n",
    "        def find(i): \n",
    "            if union[i] == i: return i\n",
    "            union[i] = find(union[i])\n",
    "            return union[i]\n",
    "        \n",
    "        # 按val从小到大遍历\n",
    "        pool = collections.defaultdict(list)\n",
    "        for val in sorted(ls.keys()): \n",
    "\n",
    "            # 用并查集合并行和列相同的元素并分组\n",
    "            for r, c in ls[val]: \n",
    "                union[find(r)] = find(c+LIM)\n",
    "            pool.clear()\n",
    "            for r, c in ls[val]: \n",
    "                pool[find(r)].append((r, c))\n",
    "\n",
    "                \n",
    "            # 行和列相同的元素，共享相同的rank\n",
    "            for group in pool.values(): \n",
    "                rank = max(max((countR[r], countC[c])) for r, c in group) + 1\n",
    "                for r, c in group: \n",
    "                    countR[r] = countC[c] = res[r][c] = rank\n",
    "                    # 重置并查集\n",
    "                    union[r] = r\n",
    "                    union[c+LIM] = c+LIM\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution: \n",
    "    def matrixRankTransform(self, matrix: List[List[int]]) -> List[List[int]]: \n",
    "        LIM = 512\n",
    "        R, C = len(matrix), len(matrix[0])\n",
    "        res = [[0]*C for _ in range(R)]\n",
    "        countR, countC = [0]*R, [0]*C\n",
    "        \n",
    "        # 按元素大小分别存储元素坐标\n",
    "        ls = collections.defaultdict(list)\n",
    "        for r, row in enumerate(matrix): \n",
    "            for c, val in enumerate(row): \n",
    "                ls[val].append((r, c))\n",
    "                \n",
    "        # 并查集用于合并行或列相同的元素\n",
    "        union = list(range(LIM*2))\n",
    "        def find(i): \n",
    "            if union[i] == i: return i\n",
    "            union[i] = find(union[i])\n",
    "            return union[i]\n",
    "        \n",
    "        # 按val从小到大遍历\n",
    "        pool = collections.defaultdict(list)\n",
    "        for val in sorted(ls.keys()): \n",
    "\n",
    "            # 用并查集合并行和列相同的元素并分组\n",
    "            for r, c in ls[val]: \n",
    "                union[find(r)] = find(c+LIM)\n",
    "            pool.clear()\n",
    "            for r, c in ls[val]: \n",
    "                pool[find(r)].append((r, c))\n",
    "\n",
    "                \n",
    "            # 行和列相同的元素，共享相同的rank\n",
    "            for group in pool.values(): \n",
    "                rank = max(max((countR[r], countC[c])) for r, c in group) + 1\n",
    "                for r, c in group: \n",
    "                    countR[r] = countC[c] = res[r][c] = rank\n",
    "                    # 重置并查集\n",
    "                    union[r] = r\n",
    "                    union[c+LIM] = c+LIM\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixRankTransform(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        LIM = 512\n",
    "        R, C = len(matrix), len(matrix[0])\n",
    "        res = [[0]*C for _ in range(R)]\n",
    "        countR, countC = [0]*R, [0]*C\n",
    "        \n",
    "        # 按元素大小分别存储元素坐标\n",
    "        ls = collections.defaultdict(list)\n",
    "        for r, row in enumerate(matrix): \n",
    "            for c, val in enumerate(row): \n",
    "                ls[val].append((r, c))\n",
    "                \n",
    "        # 并查集用于合并行或列相同的元素\n",
    "        union = list(range(LIM*2))\n",
    "        def find(i): \n",
    "            if union[i] == i: return i\n",
    "            union[i] = find(union[i])\n",
    "            return union[i]\n",
    "        \n",
    "        # 按val从小到大遍历\n",
    "        pool = collections.defaultdict(list)\n",
    "        for val in sorted(ls.keys()): \n",
    "\n",
    "            # 用并查集合并行和列相同的元素并分组\n",
    "            for r, c in ls[val]: \n",
    "                union[find(r)] = find(c+LIM)\n",
    "            pool.clear()\n",
    "            for r, c in ls[val]: \n",
    "                pool[find(r)].append((r, c))\n",
    "\n",
    "                \n",
    "            # 行和列相同的元素，共享相同的rank\n",
    "            for group in pool.values(): \n",
    "                rank = max(max((countR[r], countC[c])) for r, c in group) + 1\n",
    "                for r, c in group: \n",
    "                    countR[r] = countC[c] = res[r][c] = rank\n",
    "                    # 重置并查集\n",
    "                    union[r] = r\n",
    "                    union[c+LIM] = c+LIM\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution: \n",
    "    def matrixRankTransform(self, matrix: List[List[int]]) -> List[List[int]]: \n",
    "        LIM = 512\n",
    "        R, C = len(matrix), len(matrix[0])\n",
    "        res = [[0]*C for _ in range(R)]\n",
    "        countR, countC = [0]*R, [0]*C\n",
    "        \n",
    "        # 按元素大小分别存储元素坐标\n",
    "        ls = collections.defaultdict(list)\n",
    "        for r, row in enumerate(matrix): \n",
    "            for c, val in enumerate(row): \n",
    "                ls[val].append((r, c))\n",
    "                \n",
    "        # 并查集用于合并行或列相同的元素\n",
    "        union = list(range(LIM*2))\n",
    "        def find(i): \n",
    "            if union[i] == i: return i\n",
    "            union[i] = find(union[i])\n",
    "            return union[i]\n",
    "        \n",
    "        # 按val从小到大遍历\n",
    "        pool = collections.defaultdict(list)\n",
    "        for val in sorted(ls.keys()): \n",
    "\n",
    "            # 用并查集合并行和列相同的元素并分组\n",
    "            for r, c in ls[val]: \n",
    "                union[find(r)] = find(c+LIM)\n",
    "            pool.clear()\n",
    "            for r, c in ls[val]: \n",
    "                pool[find(r)].append((r, c))\n",
    "\n",
    "                \n",
    "            # 行和列相同的元素，共享相同的rank\n",
    "            for group in pool.values(): \n",
    "                rank = max(max((countR[r], countC[c])) for r, c in group) + 1\n",
    "                for r, c in group: \n",
    "                    countR[r] = countC[c] = res[r][c] = rank\n",
    "                    # 重置并查集\n",
    "                    union[r] = r\n",
    "                    union[c+LIM] = c+LIM\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import time\n",
    "class Solution: \n",
    "    def matrixRankTransform(self, matrix: List[List[int]]) -> List[List[int]]: \n",
    "        print(matrix)\n",
    "        LIM = 512\n",
    "        R, C = len(matrix), len(matrix[0])\n",
    "        res = [[0]*C for _ in range(R)]\n",
    "        countR, countC = [0]*R, [0]*C\n",
    "        \n",
    "        # 按元素大小分别存储元素坐标\n",
    "        ls = collections.defaultdict(list)\n",
    "        for r, row in enumerate(matrix): \n",
    "            for c, val in enumerate(row): \n",
    "                ls[val].append((r, c))\n",
    "                \n",
    "        # 并查集用于合并行或列相同的元素\n",
    "        union = list(range(LIM*2))\n",
    "        def find(i): \n",
    "            if union[i] == i: return i\n",
    "            union[i] = find(union[i])\n",
    "            return union[i]\n",
    "        \n",
    "        # 按val从小到大遍历\n",
    "        pool = collections.defaultdict(list)\n",
    "        for val in sorted(ls.keys()): \n",
    "\n",
    "            # 用并查集合并行和列相同的元素并分组\n",
    "            for r, c in ls[val]: \n",
    "                union[find(r)] = find(c+LIM)\n",
    "            pool.clear()\n",
    "            for r, c in ls[val]: \n",
    "                pool[find(r)].append((r, c))\n",
    "\n",
    "                \n",
    "            # 行和列相同的元素，共享相同的rank\n",
    "            for group in pool.values(): \n",
    "                rank = max(max((countR[r], countC[c])) for r, c in group) + 1\n",
    "                for r, c in group: \n",
    "                    countR[r] = countC[c] = res[r][c] = rank\n",
    "                    # 重置并查集\n",
    "                    union[r] = r\n",
    "                    union[c+LIM] = c+LIM\n",
    "        time.sleep(0.2)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixRankTransform(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "\n",
    "        val_pos = defaultdict(list) # 每个val出现的所有坐标\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                val_pos[matrix[i][j]].append((i, j))\n",
    "        \n",
    "        # 行列并查集，前m个下标表示行号、后n个下标表示列号\n",
    "        # 对val_pos中每个值，遍历其所有坐标，对每个坐标(i, j)的行列进行自关联\n",
    "        # 在以上过程中，如果两个相同元素出现在同一行或同一列，他们的行号、列号会串联在同一合集中\n",
    "        # 列如：(a, b)坐标时将“行a”和“列b”关联，(c, b)坐标时将“行c”与“列b”“行a”关联\n",
    "        # 借此可以将每组相同元素分成若干小组，每小组的元素组成由同行或同列关系构成的网络(他们将享有相同的rank)\n",
    "        union = list(range(m + n))\n",
    "        def find(a):\n",
    "            if union[a] != a: union[a] = find(union[a])\n",
    "            return union[a]\n",
    "        def merge(row, col):\n",
    "            union[find(row)] = find(col + m) # 列储存在union的后半部分，需要+m进行转换\n",
    "\n",
    "        rows_rank, cols_rank = [0] * m, [0] * n # 每一行、列当前已标至的rank\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for val in sorted(val_pos.keys()):\n",
    "            union = list(range(m + n)) # 对每个val，相同元素的行列关系网络需重新开始计算\n",
    "            for row, col in val_pos[val]: merge(row, col) # 将相同元素按是否同行列分为若干组\n",
    "            groups = defaultdict(list) # 将分组具象化，同组的所有元素的union值最终指向该组第一个元素的col号\n",
    "            for row, col in val_pos[val]: groups[find(row)].append((row, col))\n",
    "\n",
    "            for g in groups.values(): # 同一小组的享有相同rank，需要一起处理\n",
    "                rank = 0\n",
    "                for row, col in g: # 找到这个共享的rank，该rank为组内各元素独立rank的最大值+1\n",
    "                    rank = max(rank, rows_rank[row] + 1, cols_rank[col] + 1)\n",
    "                for row, col in g: # 将rank赋予ans\n",
    "                    ans[row][col] = rank\n",
    "                    rows_rank[row] = cols_rank[col] = rank\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixRankTransform(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "\n",
    "        val_pos = defaultdict(list) # 每个val出现的所有坐标\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                val_pos[matrix[i][j]].append((i, j))\n",
    "        \n",
    "        # 行列并查集，前m个下标表示行号、后n个下标表示列号\n",
    "        # 对val_pos中每个值，遍历其所有坐标，对每个坐标(i, j)的行列进行自关联\n",
    "        # 在以上过程中，如果两个相同元素出现在同一行或同一列，他们的行号、列号会串联在同一合集中\n",
    "        # 列如：(a, b)坐标时将“行a”和“列b”关联，(c, b)坐标时将“行c”与“列b”“行a”关联\n",
    "        # 借此可以将每组相同元素分成若干小组，每小组的元素组成由同行或同列关系构成的网络(他们将享有相同的rank)\n",
    "        union = list(range(m + n))\n",
    "        def find(a):\n",
    "            if union[a] != a: union[a] = find(union[a])\n",
    "            return union[a]\n",
    "        def merge(row, col):\n",
    "            union[find(row)] = find(col + m) # 列储存在union的后半部分，需要+m进行转换\n",
    "\n",
    "        rows_rank, cols_rank = [0] * m, [0] * n # 每一行、列当前已标至的rank\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for val in sorted(val_pos.keys()):\n",
    "            union = list(range(m + n)) # 对每个val，相同元素的行列关系网络需重新开始计算\n",
    "            for row, col in val_pos[val]: merge(row, col) # 将相同元素按是否同行列分为若干组\n",
    "            groups = defaultdict(list) # 将分组具象化，同组的所有元素的union值最终指向该组第一个元素的col号\n",
    "            for row, col in val_pos[val]: groups[find(row)].append((row, col))\n",
    "\n",
    "            for g in groups.values(): # 同一小组的享有相同rank，需要一起处理\n",
    "                rank = 0\n",
    "                for row, col in g: # 找到这个共享的rank，该rank为组内各元素独立rank的最大值+1\n",
    "                    rank = max(rank, rows_rank[row] + 1, cols_rank[col] + 1)\n",
    "                for row, col in g: # 将rank赋予ans\n",
    "                    ans[row][col] = rank\n",
    "                    rows_rank[row] = cols_rank[col] = rank\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixRankTransform(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        ans = [[0]*n for _ in range(m)]\n",
    "        r = [0]*m\n",
    "        c = [0]*n\n",
    "        d = {}\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                d[matrix[i][j]] = d.get(matrix[i][j], set())\n",
    "                d[matrix[i][j]].add((i, j))\n",
    "\n",
    "        for k in sorted(list(d.keys())):\n",
    "            rk = d[k]\n",
    "            while rk:\n",
    "                i, j = rk.pop()\n",
    "                f_x = set([i])\n",
    "                f_y = set([j])\n",
    "                f = set([(i, j)])\n",
    "                while rk:\n",
    "                    t = set()\n",
    "                    for rx, ry in rk:\n",
    "                        if rx in f_x or ry in f_y:\n",
    "                            f_x.add(rx)\n",
    "                            f_y.add(ry)\n",
    "                            t.add((rx, ry))\n",
    "                    if not t:\n",
    "                        break\n",
    "                    else:\n",
    "                        rk -= t\n",
    "                        f |= t\n",
    "                fv = 0\n",
    "                for x in f_x:\n",
    "                    fv = max(fv, r[x])\n",
    "                for y in f_y:\n",
    "                    fv = max(fv, c[y])\n",
    "                fv += 1\n",
    "\n",
    "                for x, y in f:\n",
    "                    ans[x][y] = fv\n",
    "                    r[x] = fv\n",
    "                    c[y] = fv\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixRankTransform(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        ans = [[0]*n for _ in range(m)]\n",
    "        r = [0]*m\n",
    "        c = [0]*n\n",
    "        rank = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                rank.append([matrix[i][j], i, j])\n",
    "        rank.sort(key=lambda x:-x[0])\n",
    "\n",
    "        while rank:\n",
    "            a = rank[-1][0]\n",
    "            rk = set()\n",
    "\n",
    "            while rank and rank[-1][0] == a:\n",
    "                rk.add(tuple(rank.pop()[1:]))\n",
    "\n",
    "            while rk:\n",
    "                i, j = rk.pop()\n",
    "                f_x = set([i])\n",
    "                f_y = set([j])\n",
    "                f = set([(i, j)])\n",
    "                while rk:\n",
    "                    t = set()\n",
    "                    for rx, ry in rk:\n",
    "                        if rx in f_x or ry in f_y:\n",
    "                            f_x.add(rx)\n",
    "                            f_y.add(ry)\n",
    "                            t.add((rx, ry))\n",
    "                    if not t:\n",
    "                        break\n",
    "                    else:\n",
    "                        rk -= t\n",
    "                        f |= t\n",
    "                fv = 0\n",
    "                for x in f_x:\n",
    "                    fv = max(fv, r[x])\n",
    "                for y in f_y:\n",
    "                    fv = max(fv, c[y])\n",
    "                fv += 1\n",
    "\n",
    "                for x, y in f:\n",
    "                    ans[x][y] = fv\n",
    "                    r[x] = fv\n",
    "                    c[y] = fv\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.parents = [i for i in range(n)]\n",
    "    \n",
    "    def findParents(self, u):\n",
    "        if u != self.parents[u]:\n",
    "            self.parents[u] = self.findParents(self.parents[u])\n",
    "        return self.parents[u]\n",
    "    \n",
    "    def union(self, u, v):\n",
    "        pu, pv = self.findParents(u), self.findParents(v)\n",
    "        if pu != pv:\n",
    "            self.parents[pu] = pv\n",
    "        \n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def matrixRankTransform(self, matrix: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        graph = defaultdict(list)\n",
    "        uf = UnionFind(m*n)\n",
    "        indegrees = [0] * (m*n)\n",
    "\n",
    "        # build graph\n",
    "        for i in range(m):\n",
    "            temp = []\n",
    "            for j in range(n):\n",
    "                temp.append((matrix[i][j], i*n+j))\n",
    "            temp.sort()\n",
    "            for j in range(1, n):\n",
    "                if temp[j][0] == temp[j-1][0] and uf.findParents(temp[j][1]) != uf.findParents(temp[j-1][1]):\n",
    "                    uf.union(temp[j][1], temp[j-1][1])\n",
    "                if temp[j][0] > temp[j-1][0]:\n",
    "                    graph[temp[j-1][1]].append(temp[j][1])\n",
    "                    indegrees[temp[j][1]] += 1\n",
    "        for j in range(n):\n",
    "            temp = []\n",
    "            for i in range(m):\n",
    "                temp.append((matrix[i][j], i*n+j))\n",
    "            temp.sort()\n",
    "            for i in range(1, m):\n",
    "                if temp[i][0] == temp[i-1][0] and uf.findParents(temp[i][1]) != uf.findParents(temp[i-1][1]):\n",
    "                    uf.union(temp[i][1], temp[i-1][1])\n",
    "                if temp[i][0] > temp[i-1][0]:\n",
    "                    graph[temp[i-1][1]].append(temp[i][1])\n",
    "                    indegrees[temp[i][1]] += 1\n",
    "            \n",
    "        member = defaultdict(list)\n",
    "        # 把具有相同值的点放在同一组，以他们的parents为准做拓扑排序\n",
    "        res = [[0]*n for _ in range(m)]\n",
    "        for i in range(m*n):\n",
    "            p = uf.findParents(i)\n",
    "            member[p].append(i)\n",
    "            if p != i:\n",
    "                indegrees[p] += indegrees[i]\n",
    "\n",
    "\n",
    "        q = deque()\n",
    "        for i in range(m*n):\n",
    "            if indegrees[i] == 0:\n",
    "                q.append(i)\n",
    "        rank = 1\n",
    "        while len(q) != 0:\n",
    "            l = len(q)\n",
    "            for _ in range(l):\n",
    "                curr = q.popleft()\n",
    "                # 父亲节点入度为0时，说明他下面的所有子节点都可以出队\n",
    "                for mem in member[curr]:\n",
    "                    for nxt in graph[mem]:\n",
    "                        # 更新下一个节点的入度（以下一个节点的父节点为准）\n",
    "                        indegrees[uf.findParents(nxt)] -= 1\n",
    "                        if indegrees[uf.findParents(nxt)] == 0:\n",
    "                            q.append(uf.findParents(nxt))\n",
    "                    res[mem//n][mem%n] = rank\n",
    "            rank += 1\n",
    "        return res\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
